Color halftoning is an important problem for commercial and consumer imaging devices. Color halftoning attempts to represent an image in multi-bit (e.g., 24 bits) color as an image with only a few colors, such as 4 inks (and white), and possibly increased spatial resolution. This may be done by alternating colors from the limited palette so that after the eye key averages the colors the visually perceived color appears the same as the original color.
Judging color halftoning algorithms can be difficult due to the subjective nature of vision. Specific goals in halftoning algorithms include color matching, simple computation, low graininess, artifact minimization, and reduction of post-processing effects. The relative importance of each of these goals depends upon the human viewer, the expected viewing distance, and the target image.
Color matching itself has at least two objectives: closeness of individual input and output colors and consistent errors. Computation issues include running speed, parallelizability, memory size, and complexity. Graininess can be described as the ability to perceive distinct output colors (instead of the colors blending perfectly). Perceived grainess is a function, in part, of the dpi.
Detail information may be lost due to either poor spatial resolution or poor color resolution (or a combination of both). Artifacts are a general term for anything not desirable that is a result of the algorithm (as opposed to noise), including speckles, streaks, ghosts, gridding, texture, and very importantly, false contouring (also known as banding).
Post-processing effects are a concern because a halftoned image is not necessarily ‘finished’ when it is halftoned. Various image processing operations may still be performed on it, from downsampling to compression to edge enhancement. A halftoning algorithm may affect the success and ease of these operations.
Different techniques have been devised for halftoning, including dithering, error diffusion and iterative methods. See Kang, Henry, “Digital Color Halftoning”, SPIE and IEEE Press, 1999, and Ulichney, R., “Digital Halftoning”. MIT Press, 1987. Most color halftoning techniques simply extend a black-and-white halftoning technique to each of the three color planes individually. While computationally efficient, such component-wise extensions implicitly assume a mathematical linearity of ink colors. However, the subtractive color mixing in printing is nonlinear, and thus such plane-by-plane halftoning methods are suboptimal.
Dithering consists of adding a pseudorandom 2D periodic signal to each color component of the image, then quantizing each pixel to the closest output color. The dither signal is designed to generate patterns of alternating colors that blend to the eye. Different styles of dithering include clustered dot dithering, distributed dot dithering, and ordered dot dithering. Dithering with white noise does not achieve results as visually pleasing as more ordered dithering. Dithering is known to suffer from noticeable periodic patterning. Many efforts have tried to improve dithering. The application of dithering to color is in the art. For more information, see A. Karun, et al., “New Methods for Dithering of Color Images,” Proc. of the IEEE Workshop on Nonlinear Signal/Image Processing, 1995.
While dithering is a point process (i.e., the output at each pixel depends only on the input pixel and possibly external factors like the dither signal), error diffusion diffuses the quantization error at each pixel to its neighboring pixels based on a directional spatial filter that sends a portion of the error in each forward direction. As a result, the error diffusion halftoning process adds high frequency noise. Since the goal is for the eye to blend the colors and not notice the actual mosaic of colors, this highpass filter effect of error diffusion exploits the eyes' insensitivity to high frequency noise. Thus, error diffusion yields a blue spatial spectrum. The idea that this blue noise is more visually pleasing is well-established.
Error diffusion works well in practice, giving good image quality at medium ink densities and naturally sharpening edges. See Floyd, R. W., Steinberg, L., “An adaptive algorithm for spatial greyscale”, Proceedings of the Society for Information Display, vol 17, no 2, pg 75–77, 1976. However, error diffusion has some drawbacks. It is a greedy algorithm in that it locally optimizes; that is, it does the best job it can at each pixel in space. Since the error is diffused forward, it is directional and cannot provide true joint optimization over a local region. An error may get diffused far beyond the point at which the eye is averaging color. Error diffusion artifacts include speckles, streaks, transient and edge effects, and grid effects at certain intensities. The feedback loop required for error diffusion can be a hindrance to parallel implementation of the algorithm. Error diffusion techniques that are block-based include Fan's work. For more information on Fan's work, see Kang, Henry. “Digital Color Halftoning.” SPIE and IEEE Press, 1999, and more recently, Damera-Venkata's work, Damera-Venkata N., Evans, B. “FM Hafltoning via block error diffusion.” Proc. of IEEE ICIP, pg. 1081–1084, 2001.
Improvements have been made in error diffusion over many years. Efforts have been made in such directions as minimizing structural artifacts, making the feedback filter adaptive, and using neural networks.
Also, there are successful black-and-white halftoning techniques that use perceptual and printer models, but these require complex extensions for color halftoning.
There are additional black and white algorithms that consider the idea of mean-matching. For example, one multiscale halftoning algorithm begins at the resolution of the whole image and sets the output image average gray level equal to the input image average gray level. Then the next higher level of resolution proportionately splits up the average gray level amongst four quadrants based on their average gray levels. This process continues through the levels of resolution until each pixel is quantized black or white. For example, see Breaux, et al., “Wavelet Methods for Compression, Rendering, and Descreening in Digital Halftoning,” SPIE Vol. 3078, 1997; Breaux N. and Chu C. H. “Wavelet Methods For Compression, Rendering, And Descreening In Digital Halftoning,” Proc. of the SPIE, vol 3078, pg 656–667, 1997 (calculate wavelet averages and then use dithering to approximate these gray-level averages); P. W. Wong, “Halftoning by Multiscale Dot Distribution,” Proc. IEEE Int. Conference on Image Processing, Vol. III, 1995; P. W. Wong, “Mean matching Halftoning on a Rotated Quad-tree Structure,” Human Vision and Electronic Imaging,” Proc. SPIE 2657, 1996 (matching the average gray levels of the input and output image at various resolutions). See also Katsavoundidis, I., and Kuo, C. C., “A Recursive Multiscale Error-Diffusion Technique for Digital Halftoning”, SPIE Conference Proceedings, vol 2094, 1993, and Katsavoundidis, I., and Kuo, C. C., “A Multiscale Error Diffusion Technique For Digital Halftoning,” IEEE Transactions on Image Processing, vol 6, no 3, March 1997 (Katsavounidis and Kuo aim to match intensities at different resolutions, but use a ‘multiscale error-diffusion’ technique).
In another prior art solution, the average gray levels of the input and output images are generated at various resolutions. In still another prior art solution, wavelet averages are calculated and then dithering is used to approximate these gray-level averages. More specifically, the image is first compressed with wavelets and then the wavelet coefficients are used at each level as the average gray level to determine how white dots should be divvied up amongst the quadrants. This technique does not go down to the pixel level and tessellates the chosen number of white dots using a clustered dot or dispersed dot dither. Their results suffer from horizontal and vertical artifacts and false contouring.